#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define HASH_TABLE_SIZE 101  // 哈希表大小（素数减少冲突）
int min(int a,int b){
    return a<b?a:b;
}
// ---------------------- 数据结构定义 ----------------------
// 路口（哈希表节点）
typedef struct Intersection {
    int id;          // 路口ID
    int flow;        // 交通流量
    struct Intersection* next; // 哈希冲突链表
} Intersection;

// 道路（邻接表节点）
typedef struct Road {
    int to;          // 目标路口ID
    int length;      // 长度
    int original_time; // 原始通行时间
    int current_time;  // 实时通行时间（事件影响）
    int original_capacity; // 原始承载量
    int current_capacity;  // 实时承载量（事件影响）
    struct Road* next; // 下一条道路
} Road;

// 邻接表节点（哈希表存储，ID→Road链表）
typedef struct AdjNode {
    int id;          // 路口ID
    Road* roads;     // 道路链表头
    struct AdjNode* next; // 哈希冲突链表
} AdjNode;

// 交通事件（优先队列元素，按结束时间排序）
typedef struct TrafficEvent {
    int event_id;    // 事件ID
    int start;       // 道路起点ID
    int end;         // 道路终点ID
    int end_time;    // 事件结束时间
    int new_time;    // 事件期间通行时间
    int new_capacity;// 事件期间承载量
} TrafficEvent;

// 图结构
typedef struct Graph {
    Intersection** intersections; // 路口哈希表
    AdjNode** adj_list;           // 邻接表哈希表
    TrafficEvent** event_heap;    // 事件优先队列（最小堆）
    int heap_size;                // 堆大小
} Graph;


// ---------------------- 自定义哈希表实现 ----------------------
// 哈希函数（简单取模）
unsigned int hash(int key) {
    return key % HASH_TABLE_SIZE;
}

// 添加路口到哈希表
void add_intersection(Graph* g, int id) {
    unsigned int idx = hash(id);
    Intersection* new_inter = malloc(sizeof(Intersection));
    new_inter->id = id;
    new_inter->flow = 0;
    new_inter->next = g->intersections[idx];
    g->intersections[idx] = new_inter;
}

// 查找路口
Intersection* find_intersection(Graph* g, int id) {
    unsigned int idx = hash(id);
    Intersection* inter = g->intersections[idx];
    while (inter) {
        if (inter->id == id) return inter;
        inter = inter->next;
    }
    return NULL;
}

// 添加邻接表节点
AdjNode* find_or_create_adj(Graph* g, int id) {
    unsigned int idx = hash(id);
    AdjNode* adj = g->adj_list[idx];
    while (adj) {
        if (adj->id == id) return adj;
        adj = adj->next;
    }
    // 创建新节点
    adj = malloc(sizeof(AdjNode));
    adj->id = id;
    adj->roads = NULL;
    adj->next = g->adj_list[idx];
    g->adj_list[idx] = adj;
    return adj;
}


// ---------------------- 优先队列（事件堆，最小堆） ----------------------
// 堆上浮
void heap_up(Graph* g, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (g->event_heap[parent]->end_time <= g->event_heap[index]->end_time) break;
        // 交换
        TrafficEvent* temp = g->event_heap[parent];
        g->event_heap[parent] = g->event_heap[index];
        g->event_heap[index] = temp;
        index = parent;
    }
}

// 添加事件到堆
void add_event(Graph* g, TrafficEvent* event) {
    if (g->heap_size >= 1024) { // 动态扩容
        g->event_heap = realloc(g->event_heap, sizeof(TrafficEvent*) * (g->heap_size + 1024));
    }
    g->event_heap[g->heap_size] = event;
    heap_up(g, g->heap_size);
    g->heap_size++;
}

// 堆下沉
void heap_down(Graph* g, int index) {
    int n = g->heap_size;
    while (2 * index + 1 < n) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int min_idx = left;
        if (right < n && g->event_heap[right]->end_time < g->event_heap[left]->end_time) {
            min_idx = right;
        }
        if (g->event_heap[index]->end_time <= g->event_heap[min_idx]->end_time) break;
        // 交换
        TrafficEvent* temp = g->event_heap[index];
        g->event_heap[index] = g->event_heap[min_idx];
        g->event_heap[min_idx] = temp;
        index = min_idx;
    }
}

// 处理已结束的事件（恢复道路属性）
void process_events(Graph* g, int current_time) {
    while (g->heap_size > 0 && g->event_heap[0]->end_time <= current_time) {
        // 取出堆顶事件
        TrafficEvent* event = g->event_heap[0];
        g->event_heap[0] = g->event_heap[--g->heap_size];
        heap_down(g, 0);
        
        // 恢复双向道路的原始属性
        AdjNode* adj_start = find_or_create_adj(g, event->start);
        Road* road = adj_start->roads;
        while (road) {
            if (road->to == event->end) {
                road->current_time = road->original_time;
                road->current_capacity = road->original_capacity;
                break;
            }
            road = road->next;
        }
        
        AdjNode* adj_end = find_or_create_adj(g, event->end);
        road = adj_end->roads;
        while (road) {
            if (road->to == event->start) {
                road->current_time = road->original_time;
                road->current_capacity = road->original_capacity;
                break;
            }
            road = road->next;
        }
        
        free(event); // 释放事件内存
    }
}


// ---------------------- 图操作：添加道路 ----------------------
void add_road(Graph* g, int from, int to, int length, int time, int capacity) {
    // 添加 from → to 的道路
    Road* road = malloc(sizeof(Road));
    road->to = to;
    road->length = length;
    road->original_time = time;
    road->current_time = time;
    road->original_capacity = capacity;
    road->current_capacity = capacity;
    road->next = NULL;
    
    AdjNode* adj = find_or_create_adj(g, from);
    road->next = adj->roads;
    adj->roads = road;
    
    // 添加 to → from 的道路（双向）
    road = malloc(sizeof(Road));
    road->to = from;
    road->length = length;
    road->original_time = time;
    road->current_time = time;
    road->original_capacity = capacity;
    road->current_capacity = capacity;
    road->next = NULL;
    
    adj = find_or_create_adj(g, to);
    road->next = adj->roads;
    adj->roads = road;
}


// ---------------------- 图遍历：DFS & BFS ----------------------
// DFS（递归）
void dfs_recursive(Graph* g, int start, int* visited, int* count) {
    AdjNode* adj = find_or_create_adj(g, start);
    visited[start] = 1;
    (*count)++;
    
    Road* road = adj->roads;
    while (road) {
        if (!visited[road->to]) {
            dfs_recursive(g, road->to, visited, count);
        }
        road = road->next;
    }
}

// DFS入口（返回访问节点数，检查连通性）
int dfs(Graph* g, int start) {
    // 确定最大ID（用于分配visited数组）
    int max_id = 0;
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        Intersection* inter = g->intersections[i];
        while (inter) {
            if (inter->id > max_id) max_id = inter->id;
            inter = inter->next;
        }
    }
    int* visited = calloc(max_id + 1, sizeof(int));
    int count = 0;
    dfs_recursive(g, start, visited, &count);
    free(visited);
    return count;
}

// BFS（队列实现）
int bfs(Graph* g, int start) {
    // 确定最大ID
    int max_id = 0;
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        Intersection* inter = g->intersections[i];
        while (inter) {
            if (inter->id > max_id) max_id = inter->id;
            inter = inter->next;
        }
    }
    int* visited = calloc(max_id + 1, sizeof(int));
    int count = 0;
    
    // 队列（简单链表实现）
    typedef struct QueueNode { int id; struct QueueNode* next; } QueueNode;
    QueueNode *front = NULL, *rear = NULL;
    
    // 入队起点
    QueueNode* node = malloc(sizeof(QueueNode));
    node->id = start;
    node->next = NULL;
    front = rear = node;
    visited[start] = 1;
    count++;
    
    while (front) {
        int u = front->id;
        QueueNode* temp = front;
        front = front->next;
        free(temp);
        
        AdjNode* adj = find_or_create_adj(g, u);
        Road* road = adj->roads;
        while (road) {
            int v = road->to;
            if (!visited[v]) {
                visited[v] = 1;
                count++;
                QueueNode* new_node = malloc(sizeof(QueueNode));
                new_node->id = v;
                new_node->next = NULL;
                if (!rear) front = rear = new_node;
                else { rear->next = new_node; rear = new_node; }
            }
            road = road->next;
        }
    }
    free(visited);
    return count;
}


// ---------------------- 最短路径：迪杰斯特拉 + 贪心 ----------------------
// 辅助结构体：存储距离（时间）、承载量、前驱
typedef struct DijkstraNode {
    int time;    // 最短时间
    int capacity;// 路径最小承载量
    int prev;    // 前驱路口ID
} DijkstraNode;

// 迪杰斯特拉优先队列元素（时间升序，承载量降序）
typedef struct DijkstraHeapElem {
    int time;        // 时间
    int neg_capacity;// 承载量的负数（用于堆排序）
    int id;          // 路口ID
} DijkstraHeapElem;

// 堆上浮（迪杰斯特拉专用）
void dijkstra_heap_up(DijkstraHeapElem* heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[parent].time < heap[index].time) break;
        if (heap[parent].time == heap[index].time && heap[parent].neg_capacity < heap[index].neg_capacity) break;
        // 交换
        DijkstraHeapElem temp = heap[parent];
        heap[parent] = heap[index];
        heap[index] = temp;
        index = parent;
    }
}

// 堆下沉（迪杰斯特拉专用）
void dijkstra_heap_down(DijkstraHeapElem* heap, int index, int heap_size) {
    while (2 * index + 1 < heap_size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int min_idx = left;
        if (right < heap_size) {
            if (heap[right].time < heap[left].time) min_idx = right;
            else if (heap[right].time == heap[left].time && heap[right].neg_capacity < heap[left].neg_capacity) min_idx = right;
        }
        if (heap[index].time < heap[min_idx].time) break;
        if (heap[index].time == heap[min_idx].time && heap[index].neg_capacity < heap[min_idx].neg_capacity) break;
        // 交换
        DijkstraHeapElem temp = heap[index];
        heap[index] = heap[min_idx];
        heap[min_idx] = temp;
        index = min_idx;
    }
}

// 迪杰斯特拉算法：返回路径数组，path_len为路径长度
int* dijkstra(Graph* g, int start, int end, int current_time, int* path_len) {
    process_events(g, current_time); // 先处理已结束的事件
    
    // 确定最大ID
    int max_id = 0;
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        Intersection* inter = g->intersections[i];
        while (inter) {
            if (inter->id > max_id) max_id = inter->id;
            inter = inter->next;
        }
    }
    
    DijkstraNode* nodes = malloc((max_id + 1) * sizeof(DijkstraNode));
    for (int i = 0; i <= max_id; i++) {
        nodes[i].time = INT_MAX;
        nodes[i].capacity = 0;
        nodes[i].prev = -1;
    }
    nodes[start].time = 0;
    nodes[start].capacity = INT_MAX; // 起点承载量视为无穷大
    
    // 优先队列初始化
    DijkstraHeapElem* heap = malloc(1024 * sizeof(DijkstraHeapElem)); // 动态扩容
    int heap_size = 0;
    heap[heap_size].time = 0;
    heap[heap_size].neg_capacity = -INT_MAX;
    heap[heap_size].id = start;
    heap_size++;
    dijkstra_heap_up(heap, heap_size - 1);
    
    while (heap_size > 0) {
        // 取出堆顶
        DijkstraHeapElem top = heap[0];
        heap[0] = heap[--heap_size];
        dijkstra_heap_down(heap, 0, heap_size);
        
        int u = top.id;
        if (u == end) break; // 到达终点
        if (top.time > nodes[u].time) continue; // 旧数据，跳过
        if (top.time == nodes[u].time && -top.neg_capacity < nodes[u].capacity) continue;
        
        // 遍历邻接道路
        AdjNode* adj = find_or_create_adj(g, u);
        Road* road = adj->roads;
        while (road) {
            int v = road->to;
            int new_time = top.time + road->current_time;
            int new_capacity = min(-top.neg_capacity, road->current_capacity);
            
            // 松弛操作：更短时间，或同时间但承载量更大
            if (new_time < nodes[v].time) {
                nodes[v].time = new_time;
                nodes[v].capacity = new_capacity;
                nodes[v].prev = u;
                heap[heap_size].time = new_time;
                heap[heap_size].neg_capacity = -new_capacity;
                heap[heap_size].id = v;
                heap_size++;
                dijkstra_heap_up(heap, heap_size - 1);
            } else if (new_time == nodes[v].time && new_capacity > nodes[v].capacity) {
                nodes[v].capacity = new_capacity;
                nodes[v].prev = u;
                heap[heap_size].time = new_time;
                heap[heap_size].neg_capacity = -new_capacity;
                heap[heap_size].id = v;
                heap_size++;
                dijkstra_heap_up(heap, heap_size - 1);
            }
            road = road->next;
        }
    }
    
    // 构建路径
    if (nodes[end].time == INT_MAX) {
        *path_len = 0;
        free(nodes);
        free(heap);
        return NULL;
    }
    int* path = malloc((max_id + 1) * sizeof(int));
    int len = 0;
    for (int i = end; i != -1; i = nodes[i].prev) {
        path[len++] = i;
    }
    // 反转路径
    for (int i = 0; i < len / 2; i++) {
        int temp = path[i];
        path[i] = path[len - 1 - i];
        path[len - 1 - i] = temp;
    }
    *path_len = len;
    
    // 统计流量：路径上的路口流量+1
    for (int i = 0; i < len; i++) {
        Intersection* inter = find_intersection(g, path[i]);
        if (inter) inter->flow++;
    }
    
    free(nodes);
    free(heap);
    return path;
}


// ---------------------- 流量排序：堆排序 ----------------------
// 堆化（最大堆，按流量降序）
void heapify_flow(Intersection** arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left]->flow > arr[largest]->flow) largest = left;
    if (right < n && arr[right]->flow > arr[largest]->flow) largest = right;
    if (largest != i) {
        Intersection* temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify_flow(arr, n, largest);
    }
}

// 堆排序：返回降序的路口数组
Intersection** heap_sort_flow(Graph* g, int* count) {
    // 收集所有路口
    int num = 0;
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        Intersection* inter = g->intersections[i];
        while (inter) {
            num++;
            inter = inter->next;
        }
    }
    
    Intersection** arr = malloc(num * sizeof(Intersection*));
    int i = 0;
    for (int j = 0; j < HASH_TABLE_SIZE; j++) {
        Intersection* inter = g->intersections[j];
        while (inter) {
            arr[i++] = inter;
            inter = inter->next;
        }
    }
    
    // 构建最大堆
    for (int j = num / 2 - 1; j >= 0; j--) {
        heapify_flow(arr, num, j);
    }
    // 排序
    for (int j = num - 1; j > 0; j--) {
        Intersection* temp = arr[0];
        arr[0] = arr[j];
        arr[j] = temp;
        heapify_flow(arr, j, 0);
    }
    
    *count = num;
    return arr;
}


// ---------------------- 初始化与销毁 ----------------------
Graph* graph_create() {
    Graph* g = malloc(sizeof(Graph));
    g->intersections = calloc(HASH_TABLE_SIZE, sizeof(Intersection*));
    g->adj_list = calloc(HASH_TABLE_SIZE, sizeof(AdjNode*));
    g->event_heap = malloc(1024 * sizeof(TrafficEvent*));
    g->heap_size = 0;
    return g;
}

void graph_destroy(Graph* g) {
    // 释放邻接表
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        AdjNode* adj = g->adj_list[i];
        while (adj) {
            AdjNode* temp = adj;
            Road* road = adj->roads;
            while (road) {
                Road* road_temp = road;
                road = road->next;
                free(road_temp);
            }
            adj = adj->next;
            free(temp);
        }
    }
    
    // 释放路口哈希表
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        Intersection* inter = g->intersections[i];
        while (inter) {
            Intersection* temp = inter;
            inter = inter->next;
            free(temp);
        }
    }
    
    // 释放事件堆剩余事件
    for (int i = 0; i < g->heap_size; i++) {
        free(g->event_heap[i]);
    }
    
    free(g->intersections);
    free(g->adj_list);
    free(g->event_heap);
    free(g);
}


// ---------------------- 测试主函数 ----------------------
int main() {
    Graph* g = graph_create();
    
    // 添加路口
    for (int i = 1; i <= 6; i++) add_intersection(g, i);
    
    // 添加道路
    add_road(g, 1, 2, 5, 3, 120);
    add_road(g, 1, 3, 8, 5, 150);
    add_road(g, 2, 4, 10, 6, 100);
    add_road(g, 2, 5, 7, 4, 80);
    add_road(g, 3, 5, 5, 3, 130);
    add_road(g, 4, 6, 6, 3, 90);
    add_road(g, 5, 6, 4, 2, 110);
    
    // 添加多个事件
    TrafficEvent* event1 = malloc(sizeof(TrafficEvent));
    event1->event_id = 1;
    event1->start = 2;
    event1->end = 4;
    event1->end_time = 30;
    event1->new_time = 12;
    event1->new_capacity = 60;
    add_event(g, event1);
    
    TrafficEvent* event2 = malloc(sizeof(TrafficEvent));
    event2->event_id = 2;
    event2->start = 3;
    event2->end = 5;
    event2->end_time = 25;
    event2->new_time = 8;
    event2->new_capacity = 70;
    add_event(g, event2);
    
    // 测试不同时间的路径规划
    printf("时间10（两事件均生效）：\n");
    int path_len;
    int* path = dijkstra(g, 1, 6, 10, &path_len);
    printf("路径（1→6）：");
    for (int i = 0; i < path_len; i++) printf("%d ", path[i]);
    printf("\n");
    free(path);
    
    printf("时间26（仅事件1生效）：\n");
    path = dijkstra(g, 1, 6, 26, &path_len);
    printf("路径（1→6）：");
    for (int i = 0; i < path_len; i++) printf("%d ", path[i]);
    printf("\n");
    free(path);
    
    printf("时间31（两事件均结束）：\n");
    path = dijkstra(g, 1, 6, 31, &path_len);
    printf("路径（1→6）：");
    for (int i = 0; i < path_len; i++) printf("%d ", path[i]);
    printf("\n");
    free(path);
    
    // 测试连通性
    printf("DFS遍历节点数（从1）：%d\n", dfs(g, 1));
    printf("BFS遍历节点数（从1）：%d\n", bfs(g, 1));
    
    graph_destroy(g);
    return 0;
}